package com.hqq.leetcode.dp;

/**
 * Triangle 数字三角形
 * Description:
 * Given a triangle, find the minimum path sum from top to bottom.
 * Each step you may move to adjacent numbers on the row below.
 * <p>
 * Input:
 * [
 * ---[2],
 * --[3,4],
 * -[6,5,7],
 * [4,1,8,3]
 * ]
 * Output:
 * 11
 * Analysis:
 * 2 + 3 + 5 + 1 = 11
 * Created by heqianqian on 2017/9/15.
 */
public class Triangle {

    public static void main(String[] args) {
        /*data preparation*/
        int[][] array = new int[4][];
        array[0] = new int[1];
        array[0][0] = 2;
        array[1] = new int[2];
        array[1][0] = 3;
        array[1][1] = 4;
        array[2] = new int[3];
        array[2][0] = 6;
        array[2][1] = 5;
        array[2][2] = 7;
        array[3] = new int[4];
        array[3][0] = 4;
        array[3][1] = 1;
        array[3][2] = 8;
        array[3][3] = 3;

        Triangle triangle = new Triangle();
        int result = triangle.minimumTotal2(array);
        System.out.println(result);
    }

    public int minimumTotal(int[][] triangle) {
        /*直接修改原数组的方法 使得triangle[i][j]为从根到该节点的最短路径*/
        int n = triangle.length;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < triangle[i].length; j++) {
                if (j == 0) {
                    //如果是每行的第一个元素 等于上一行的该列元素加上当前元素
                    triangle[i][j] += triangle[i - 1][j];
                } else if (j == triangle[i].length - 1) {
                    //如果是每行的最后一个元素 等于上一行的前一列的元素加上当前元素
                    triangle[i][j] += triangle[i - 1][j - 1];
                } else {
                    triangle[i][j] += Math.min(triangle[i - 1][j - 1], triangle[i - 1][j]);
                }
            }
        }
        //遍历最后一行 找到最小的元素
        int res = triangle[n - 1][0];
        for (int i = 1; i < triangle[n - 1].length; i++) {
            res = Math.min(res, triangle[n - 1][i]);
        }
        return res;
    }

    /*复制triangle的最后一行 每次选出当前元素和后一个元素的最小值和上一个元素之和作为当前元素的值*/
    public int minimumTotal2(int[][] triangle) {
        int n = triangle.length;
        //复制triangle的最后一行 用于更新
        int[] dp = triangle[triangle.length - 1];
        for (int i = n - 2; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                dp[j] = Math.min(dp[j], dp[j + 1]) + triangle[i][j];
            }
        }
        return dp[0];
    }
}
